Packrat Parsing: Simple, Powerful, Lazy, Linear Time
2002 Bryan Ford
ソースコードもある
Uses memoization to provide backtracking and unlimited lookahead in a linear-time parser
memoizationによりパースが線形の時間ということ?
Abstract
Packrat parsing is a novel technique for implementing parsers in a lazy functional programming language.
packrat:モリネズミ、必要ないものを溜め込む人(ウィズダム英和辞典)